/**
 * @author VernHe
 * @date 2021年07月16日 14:04
 */
public class Solution_0151 {
    public static String reverseWords(String s) {
        if (null == s) {
            return "";
        }
        // 先消除空格
        // 字符数组
        char[] chars = s.toCharArray();
        // 消除空格后有效的字符串长度
        int len = 0;
        // cur表示当前可以放字符的地方，i表示正在遍历的位置
        int cur = 0;
        // 相当于index = -1处是空格
        boolean isSpace = true;
        for (int i = 0; i < chars.length; i++) {
            // 如果当前i位置不是空格就交换到前面去
            if (chars[i] != ' ') {
                chars[cur++] = chars[i];
                // 交换到前面后，前面就是非空格了
                isSpace = false;
            } else if (isSpace == false) {
                // 如果是空格并且之前不是空格,就把空格交换过去
                chars[cur++] = chars[i];
                // 空格交换到前面后，前面就变成了空格了
                isSpace = true;
            }
        }

        // 字符长度
        len = isSpace ? (cur - 1) : cur;
        // 如果全是空格，最终len = -1
        if (len == -1) {
            return "";
        }
        // 翻转整个字符串
        revers(chars, 0, len);
        // 前一个空格的下标
        int preIndex = -1;
        // 从左往右翻转每一个单词
        for (int i = 0; i < len; i++) {
            if (chars[i] == ' ') {
                revers(chars, preIndex + 1, i);
                preIndex = i;
            }
        }
        // 当退出循环的时候i = len，此时最后一个字符串没有进行反转
        revers(chars, preIndex + 1, len);
        return new String(chars, 0, len);
    }

    /**
     * 翻转[li,ri)之间的字符
     *
     * @param chars
     * @param li
     * @param ri
     */
    private static void revers(char[] chars, int li, int ri) {
        ri--;
        while (li < ri) {
            char temp = chars[li];
            chars[li++] = chars[ri];
            chars[ri--] = temp;
        }
    }

    public static void main(String[] args) {
        System.out.println(reverseWords("1 2 3 4 5 6 7 8 9"));
        System.out.println(reverseWords("hello word !"));
    }
}
